package algorithm.dynamic;

/**
 * 01背包问题
 *
 * 416.Partition Equal Subset Sum
 * leetcode : https://leetcode.com/problems/partition-equal-subset-sum/
 * Difficulty : Medium
 *
 * 给一个非空，只包含正数的整形数组。判断这个数组是否可以拆成两个和相等的子数组
 * 数组元组大小不超过100.
 * 数组长度不超过200.
 *
 * Example:
 * Input:[1,5,11,1]
 * Output: true
 *
 *
 * 参考：
 * 分割等和子集：https://blog.csdn.net/qq_26410101/article/details/80806463
 * 背包问题详解：https://blog.csdn.net/na_beginning/article/details/62884939
 * 动态规划之01背包问题以及leetcode示例：https://blog.csdn.net/c_j33/article/details/79151061
 *
 *
 * 思路：
 * 典型的01背包问题。
 * 一个简单的思路是，转化为，求其中子序列的和是否可以为 sum/2.
 *
 *
 * DP解法不是最快的。
 * 还有其他两种更快的解法
 *
 * @Author Antony
 * @Since 2018/11/12 14:15
 */
public class PartitionEqualSubsetSum {

    public static void main(String[] args) {
        int[] arr = new int[]{1,5,11,5};
        System.out.println(canPartition(arr));
    }


    /**
     * DP解法.不是最快的
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        int sums = 0;
        for(int num : nums){
            sums += num;
        }
        if(sums%2 != 0){
            return false;   // 验证求和是否可以被2整除，不能的话就直接返回false
        }

        int halfSum = sums/2;
        return dp_one_dimension(nums, halfSum);
    }

    /**
     * leetcode : 30ms - beats 39.96%
     * dp[i][j] 表示 前i个元素中挑出的子序列，是否可以计算出和为j
     *
     * 那么由dp[i][j]的结果。可以得出两种情况(或的关系,满足其中一个即可)：
     * 1) dp[i-1][j]=true
     * 2) dp[i-1][j-nums[i]]=true
     *
     * 二维递推公式
     * 即：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
     *
     * 则最后返回 dp[nums.length][target] 的结果即可
     * @param nums
     * @param target
     * @return
     */
    private static boolean dp(int[] nums, int target){
        // 创建数组的长度都要+1。因为有dp[0][0] 存在
        boolean[][] dp = new boolean[nums.length+1][target+1];
        dp[0][0] = true;
        for(int i=1; i<=nums.length; i++){
            for(int j=0; j<=target; j++){
                if(dp[i-1][j]){
                    dp[i][j] = true;
                    continue;
                }
                dp[i][j] = j-nums[i-1] >=0 && dp[i-1][j-nums[i-1]]==true;
            }
        }
        return dp[nums.length][target];
    }


    /**
     * 可以优化为一维数组
     * 13ms - beats 78.21%
     *
     * 我们其实只需要上一层i-1的状态，所以我们把二维数组压缩为一维，递推公式如下：
     * dp[j] = dp[j] || dp[j - nums[i]];  j>=nums[i-1]
     * @param nums
     * @param target
     * @return
     */
    private static boolean dp_one_dimension(int[] nums, int target){
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for(int i=0; i<nums.length; i++){
            for(int t=target; t>0; t--){    // 此处注意，内层循环从大到小，以免被覆盖
                if(t >= nums[i]){
                    dp[t] = dp[t] || dp[t-nums[i]];
                }
            }
        }
        return dp[target];
    }
}
